package com.tree.stack;

import java.util.*;

/**
 * @ClassName com.tree.stack
 * Description:496. 下一个更大元素 I
 * <p>
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。



示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
 * </p>
 * @Author tree
 * @Date 1/27/24 9:42 PM
 * @Version 1.0
 */
public class NextGreaterElement_496 {

    public static void main(String[] args) {
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        System.out.println(nextGreaterElement(nums1,nums2));
        System.out.println(nextGreaterElement2(nums1,nums2));

    }

    /**
     * 单调栈
     * https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {


        //初始化返回数组， 默认找不到为-1
        int[] res = new int[nums1.length];
        Arrays.fill(res,-1);

        // nums map， 根据值映射下标
        //key 为值， value为索引
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            map.put(nums1[i],i);
        }

        //初始化栈， 栈内存放索引， 默认第一个索引为0
        Stack<Integer> stack = new Stack<>();
        stack.add(0);

        //遍历nums2， 从1开始， 因为栈中已经存放第一个索引
        for (int i = 1; i < nums2.length; i++) {
            //1. 如果当前元素小于等于栈顶元素
            if (nums2[i] <= nums2[stack.peek()]) {
                stack.add(i);
            }
            else{
                //2. 如果当前元素大于栈顶元素
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()] ){
                    if(map.containsKey(nums2[stack.peek()])){
                        //找到第一个大于的数
                        int index = map.get(nums2[stack.peek()]);
                        res[index] = nums2[i];
                    }
                    stack.pop();
                }
                stack.add(i);

            }
        }
        return res;

    }

    public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        // map集合
        Map<Integer, Integer> map = new HashMap<>();
        // 双端队列
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {
                map.put(stack.removeLast(), nums2[i]);
            }
            // 如果初始队列为空
            stack.addLast(nums2[i]);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }
        return result;
    }


}
